In computer networks, information is constantly being moved from a source to a destination, typically in the form of packets. In the simplest situations, the source and destination are directly connected and the packet of information passes from the source to the destination, without any intermediate stages. However, in most networks, there is at least one, if not multiple, intermediate stages between the source and the destination. In order for the information to move from the source to the destination, it must be routed through a set of devices that accept the packet and pass it along a predetermined path toward the destination. These devices, referred to generically as switches, are typically configured to accept packets from some number of input ports and transmit that information to an output port, which was selected from a plurality of ports. Often, ports are capable of both receiving and transmitting, such that the input and output ports are the same physical entities.
In an ideal network, traffic arrives at an input port of a switch. The switch determines the appropriate destination for the packet and immediately transmits it to the correct output port. In such a network, there is no need for storing the packet of information inside the switch, since the switch is able to transmit the packet as soon as it receives it.
However, because of a number of factors, this ideal behavior is not realizable. For instance, if the switch receives packets on several of its input ports destined for the same output port, the switch must store the information internally, since it cannot transmit all of these different packets of information simultaneously to the same output port. In this case, the output port is said to be “congested”. This term also describes the situation in which the device to which this output port is connected is unable to receive or process packets at the rate at which they arrive for some reason. In such a case, the switch must store the packet destined for that output port internally until either the offending device is able to receive more information or the packet is discarded.
In response to this phenomenon, many networks employ a mechanism known as flow control, in which the various switches and devices in the network communicate status information with each other. In this way, it is possible to proactively detect that a switch is becoming congested and take appropriate actions. For example, if a switch is congested and no longer has space in which to store additional packets, it may communicate this information to neighboring switches. These switches then stop transmitting packets to the congested node until the congested node has space to accept the packets, so as to insure that no packets are lost. There are a number of different flow control mechanisms. One such mechanism that is employed is known as credit-based flow control.
The term “credit” is typically used to denote an amount of storage, such as 32 or 64 bytes, that is available within the receiving device. During initialization, each switch communicates to its neighboring switches the amount of internal storage space it has available for incoming packets from that switch. This amount is communicated as the number of credits that it has available to the sender. The neighboring switch records this value, and uses it to control its transmissions to that switch.
When the transmitting switch sends a packet to another switch, it decrements the number of credits that it has associated with that switch based on the size of the packet. If the packet is large, the number of credits will be reduced accordingly. As the number of available credits approaches zero, the sender stops transmission to that switch, knowing that the receiving switch will be unable to store the packets.
Meanwhile, as the receiving switch processes these packets and removes them from its memory, it “returns” the credits back to the sending switch via a flow control message. This message informs the sending switch to increment the number of credits that are available at the receiving switch, typically by the number given in the flow control message.
In this way, the sending switch never sends packets that the receiving switch is unable to store. Typically, this type of flow control is used to control communications that are part of a virtual circuit. A virtual circuit is a logical connection between two points which is assumed to be a perfect, lossless, sequenced path of communications. Therefore, it is unacceptable that a packet be lost because the receiving switch did not have sufficient space in which to store the incoming packet.
Typically, within each switch there is a memory element, or a portion of a memory element which is statically allocated to each particular virtual circuit. The amount of space allocated in a memory element to a particular virtual circuit determines the number of credits which that receiving switch has with respect to that virtual circuit.
While the static allocation of a memory element or a portion of a memory element does insure that the flow control credit mechanism operates correctly, it is not without its drawbacks. Specifically, due to the static allocation of memory between the various virtual circuits, there could be scenarios in which one virtual circuit is starved for credits, while another is completely idle. Secondly, the credit scheme requires communication from the receiver back to the sender in order to replenish the sender's credit. If the credits are not returned in a timely manner, the overall bandwidth of the network can suffer, since the sender may be waiting to receive credits before transmitting. These delays can cause congestion in the sending switch, and the congestion can spread to other parts of the network.